package com.wfm.tmp;

public class P214最短回文串 {
    // abccda  最差也就分成a+bccda
    // 前面是s1，后面是s2
    // 找到最长的s1是回文串，然后把s2翻转接到最前面
    // 时O(|s|) 空O(1) |s|=s.length
    public String shortestPalindrome(String s){
        int n = s.length();
        int base = 131,mod=1000000007;// 131 是比assic128大的最小质数，减少hash碰撞
        int best=-1;
        int left = 0,right=0,mul=1;
        for (int i = 0; i < n; i++) {
            // 求字符串hash和逆字符串hash，相等说明是回文
            left=(int)(((long)left*base+s.charAt(i))%mod);
            right=(int)(right+(long)mul*s.charAt(i))%mod;
            if(left==right){
                best=i;
            }
            mul=(int)((long)mul*base%mod);
        }
        String add = best==n-1?"":s.substring(best+1);
        StringBuilder ans = new StringBuilder(add).reverse();
        ans.append(s);
        return ans.toString();
    }
}
